package lc_2959_关闭分部的可行集合数目;

import java.util.Arrays;

public class Solution {

    public int numberOfSets(int n, int maxDistance, int[][] roads) {
        int limit = 1 << n;
        int[][] ws = new int[n][n];
        for (int j = 0; j < n; j++) {
            Arrays.fill(ws[j], 100000);
            ws[j][j] = 0;
        }
        for (int[] road : roads) {
            int u = road[0], v = road[1], w = road[2];
            ws[u][v] = Math.min(ws[u][v], w);
            ws[v][u] = Math.min(ws[v][u], w);
        }
        int ans = 0;
        for (int i = 0; i < limit; i++) {
            int[][] mn = new int[n][n];
            for (int j = 0; j < n; j++) {
                Arrays.fill(mn[j], 100000);
                // mn[j][j] = 0;
            }
            for (int k = 0; k < n; k++) {
                if (((i >> k) & 1) == 0) {
                    for (int u = 0; u < n; u++) {
                        if (((i >> u) & 1) == 0) {
                            for (int v = 0; v < n; v++) {
                                if (((i >> v) & 1) == 0) {
                                    mn[u][v] = Math.min(mn[u][v], ws[u][k] + ws[k][v]);
                                }
                            }
                        }
                    }
                }
            }
            boolean ok = true;
            for (int u = 0; u < n; u++) {
                if (((i >> u) & 1) == 0) {
                    for (int v = 0; v < n; v++) {
                        if (((i >> v) & 1) == 0 && mn[u][v] > maxDistance) {
                            ok = false;
                        }
                    }
                }
            }
            if (ok) {
                // System.out.println(Integer.toBinaryString(limit));
                ans += 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution so = new Solution();
        // n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
        // int ans = so.numberOfSets(3, 12, new int[][] { { 1, 0, 11 }, { 1, 0, 16 }, {
        // 0, 2, 13 } });
        int ans = so.numberOfSets(5, 25, new int[][] { { 1, 0, 17 }, { 1, 0, 1 }, { 2, 1, 24 }, { 3, 2, 12 },
                { 1, 0, 7 }, { 3, 2, 4 }, { 2, 1, 15 }, { 0, 4, 14 } });
        // int ans = so.numberOfSets(3, 5, new int[][] { { 0, 1, 2 }, { 1, 2, 10 }, { 0,
        // 2, 10 } });
        System.out.println(ans);

        String a = "[[1,0,17],[1,0,1],[2,1,24],[3,2,12],[1,0,7],[3,2,4],[2,1,15],[0,4,14]]";
        a = a.replace('[', '{').replace(']', '}');
        System.out.println(a);
        // a = a.substring(2, a.length() - 2);
        // System.out.println(a);
        // String[] b = a.split("],\\[");
        // for (String s : b) {
        // System.out.println(s);
        // }
    }
}